// Copyright (C) Calum Grant 2008

#include "dynamic/dynamic.hpp"
#include "dynamic/extensions.hpp"
#include <cassert>

using namespace dynamic::gc;

namespace
{
	const int default_min_object_count=1000;
	const int default_idle_factor=20;
	const int default_factor=30;

	/// Used for the head of the linked list of objects.
	class gc_object_chain : public gc_object
	{
	public:
		gc_object_chain() : gc_object(1) { }
		void mark_children(garbage_collector&) { }
	};

	/// Implements a mark-sweep garbage collector.
	class gc_impl : public garbage_collector
	{
		gc_object_chain m_chain, m_live_objects;
		int m_object_count, m_previous_gc, m_next_gc, m_next_idle_gc;
		int m_min_object_count, m_idle_factor, m_factor, m_disable_count;
	public:
		gc_impl() : 
			m_object_count(0), 
			m_previous_gc(0),
			m_next_gc(default_min_object_count),
			m_min_object_count(default_min_object_count),
			m_idle_factor(default_idle_factor),
			m_factor(default_factor),
			m_disable_count(0)
		{ }

		gc_object * chain() { return &m_chain; }

		~gc_impl()
		{
			collect();
		}

		void check_gc_integrity() const
		{
			const gc_object * chain = &m_chain;

			for(gc_object *obj = chain->next_gc_object(); obj!=chain; obj=obj->next_gc_object())
			{
			}			
		}

		void collect()
		{
#define GC_DEBUG 0

#if GC_DEBUG>=1
			std::cout << "Starting garbage collection " << std::endl;
			check_gc_integrity();
#endif

			gc_object * chain = &m_chain;

			// Step 1: Reset

			for(gc_object *obj = chain->next_gc_object(); obj!=chain; )
			{
				gc_object * next = obj->next_gc_object();

#if GC_DEBUG>=2
				std::cout << "Initializing " << obj << std::endl;
#endif
				obj->init_mark();

				if(obj->is_marked())
				{
#if GC_DEBUG>=1
					std::cout << "Found root object " << obj << std::endl;
#endif
					obj->unlink();
					obj->link_to(&m_live_objects);
				}
				obj = next;
			}

			// Step 2: Mark

			while(m_live_objects.next_gc_object() != &m_live_objects)
			{
				gc_object * obj = m_live_objects.next_gc_object();
				obj->unlink();
				obj->link_to(&m_chain);
#if GC_DEBUG>=1
				std::cout << "Marking children of " << obj << std::endl;
#endif
				obj->mark_children(*this);

			}

			// Step 3: Finalize

			int n_finalized=0, n_deleted=0;

			for(gc_object *obj = chain->next_gc_object(); obj!=chain; obj=obj->next_gc_object())
			{
				if(!obj->is_marked()) 
				{
					// This isn't implemented properly yet since
					// finalizers could ressurrect objects.
					obj->finalize();
					++n_finalized;
				}
			}

			// Step 4: Sweep

			for(gc_object *obj = chain->next_gc_object(); obj!=chain; )
			{
#if GC_DEBUG>=2
				std::cout << "Checking " << obj << " for deletion" << std::endl;
#endif
				gc_object * next = obj->next_gc_object();
				if(!obj->is_marked())
				{
#if GC_DEBUG>=2
					std::cout << "Deleting " << obj << std::endl;
#endif
					delete obj;
					--m_object_count;
					++n_deleted;
				}
				obj = next;
			}

			assert(n_finalized == n_deleted);

			m_previous_gc = m_object_count;
			set_next_gc();

			dynamic::internal::apartment_defrag();

#if GC_DEBUG>=1
			check_gc_integrity();
			std::cout << "Finished garbage collection " << std::endl;
#endif
		}

		void set_next_gc()
		{
			m_next_gc = std::max(m_min_object_count, (m_previous_gc * m_factor)/10);
			m_next_idle_gc = std::max(m_min_object_count, (m_previous_gc * m_idle_factor)/10);
		}

		void mark_reachable(gc_object* obj)
		{
#if GC_DEBUG
			std::cout << "Marking " << obj << " reachable " << std::endl;
#endif

			if(!obj->is_marked())
			{
#if GC_DEBUG
				std::cout << "Adding " << obj << " to live queue" << std::endl;
#endif
				obj->mark();
				obj->unlink();
				obj->link_to(&m_live_objects);
			}
		}

		int object_count()
		{
			return m_object_count;
		}

		void try_idle_gc()
		{
			if(m_disable_count==0 && m_object_count >= m_next_idle_gc)
			{
				collect();
			}
		}

		void check_gc()
		{
			if(m_disable_count==0 && m_object_count >= m_next_gc)
			{
				collect();
			}
		}

		void enable()
		{
			--m_disable_count;
		}

		void disable()
		{
			++m_disable_count;
		}

		void on_add_object()
		{
			++m_object_count;
			check_gc();
		}

		virtual void set_min_objects(int m)
		{
			m_min_object_count = m;
			set_next_gc();
		}

		virtual void set_idle_gc_factor(int f)
		{
			m_idle_factor = f;
			set_next_gc();
		}

		virtual void set_gc_factor(int f)
		{
			m_factor = f;
			set_next_gc();
		}
	};
}

garbage_collector::~garbage_collector()
{
}


dynamic::gc::garbage_collector * dynamic::gc::create_gc()
{
	return new gc_impl;
}


void dynamic::gc::gc_object::link()
{
	global_gc().on_add_object();	// May GC
	link_to(global_gc().chain());
}


inline void gc_object::link_to(gc_object * obj)
{
	next = obj->next;
	prev = obj;
	obj->next = this;
	next->prev = this;
}


void dynamic::gc::gc_object::unlink()
{
	prev->next = next;
	next->prev = prev;
}


void dynamic::gc_hint_collect()
{
	global_gc().try_idle_gc();
}


void dynamic::gc_force_collect()
{
	global_gc().collect();
}


void dynamic::gc_disable()
{
	global_gc().disable();
}

void dynamic::gc_enable()
{
	global_gc().enable();
}

void dynamic::gc_tune(int factor, int idle_factor, int min)
{
	global_gc().set_gc_factor(factor);
	global_gc().set_idle_gc_factor(idle_factor);
	global_gc().set_min_objects(min);
}
